"""
算法题解决方法：
哈希表、双指针、滑动窗口、堆、队列、栈、递归、分治法、贪心算法

leetbook:
* 数组和字符串：https://leetcode.cn/leetbook/read/array-and-string
* 数组类算法：https://leetcode.cn/leetbook/detail/all-about-array/
* 哈希表：https://leetcode.cn/leetbook/detail/hash-table/
* 查找表类型算法：https://leetcode.cn/leetbook/detail/all-about-lockup-table/
* 二分查找：https://leetcode.cn/leetbook/detail/binary-search/
* 队列 & 栈：https://leetcode.cn/leetbook/detail/queue-stack/
* 查找表类型算法：https://leetcode.cn/leetbook/detail/all-about-lockup-table/
* N叉树：https://leetcode.cn/leetbook/detail/n-ary-tree/
* 设计数据结构：https://leetcode.cn/leetbook/detail/designing-data-structures/
* 中级算法：https://leetcode.cn/leetbook/detail/top-interview-questions-medium/

---付费书籍---
# 滑动窗口&双指针：https://leetcode.cn/leetbook/detail/sliding-window-and-two-pointers/
# 堆：https://leetcode.cn/leetbook/detail/heap/
# 贪心算法：https://leetcode.cn/leetbook/detail/greedy/
"""

import collections
import heapq
from typing import List

"""
冒泡
"""


def func1(nums: List):
    n = len(nums)
    for i in range(n):
        for j in range(n - i - 1):  # 注意数组下标越界问题
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
    return nums


"""
快排 O(nlogn)
"""


def func2(nums: List):
    if len(nums) < 2:  # 递归出口条件
        return nums
    mid = nums[0]
    l = [x for x in nums if x < mid]  # 左边
    m = [x for x in nums if x == mid]  # 中间
    r = [x for x in nums if x > mid]  # 右边
    return func2(l) + m + func2(r)


"""
装饰器单例
"""


def func3(cls, *args, **kwargs):
    instance = {}

    def get_instance():
        if cls not in instance:
            instance[cls] = cls(*args, **kwargs)
        return instance[cls]

    return get_instance


"""
青蛙跳台阶
用 f(10) = 89 验证答案
"""
def numWays(n: int) -> int:
    # """ 递归法 """
    # if n == 1:
    #     return 1
    # elif n == 2:
    #     return 2
    # else:
    #     return numWays(n-1) + numWays(n-2)
    """ 记忆递归法 """
    x, y = 1, 2
    for _ in range(1, n):  # range(n-1)
        x, y = y, x+y
    return x


"""
第一个不重复的数字,返回数字的下标值
"""


def func4(nums: List):
    hashmap = dict()
    for k, v in enumerate(nums):
        if v in hashmap:
            hashmap[v] = -1
        hashmap[v] = k

    for k, v in hashmap.items():
        if v != -1:
            return k
    return -1


"""
35. 搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
链接：https://leetcode.cn/problems/search-insert-position
"""


def func5(nums: List, target: int):
    l, r = 0, len(nums) - 1
    while l <= r:
        m = (l + r) // 2
        if target == nums[m]:
            return m
        elif target > nums[m]:
            l = m + 1
        else:
            r = m - 1
    return l


"""
无重复字符的最长子串(滑动窗口)
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
"""


def func6(s: str):
    hashset = set()
    rk, ans, n = 0, 0, len(s)
    for i in range(n):
        if i != 0:
            hashset.remove(s[i - 1])  # 移动左指针，移出窗口的最左侧元素
        while rk < n and s[rk] not in hashset:  # 移动右指针的判断条件：1 小于数组长度；2 窗口内元素不重复
            hashset.add(s[rk])
            rk += 1
        ans = max(ans, len(hashset))  # 窗口左指针变化时，计算当前窗口大小，更新历史最大窗口长度值
    return ans


"""
347. 前 K 个高频元素
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
"""


def topKFrequent1(nums: List[int], k: int) -> List[int]:
    """ [1, 1, 1, 2, 2, 3] 2 """
    count = collections.Counter(nums)  # Counter({1: 3, 2: 2, 3: 1})  可以直接使用dict所有方法
    count_k = count.most_common(k)  # [(1, 3), (2, 2)]
    ans = [item[0] for item in count_k]
    return ans


def topKFrequent2(nums: List[int], k: int) -> List[int]:
    """ [1, 1, 1, 2, 2, 3] 2 """
    count = collections.Counter(nums)  # Counter({1: 3, 2: 2, 3: 1})  可以直接使用dict所有方法
    heap = []  # 堆 定义  堆内元素为元组
    for key, val in count.items():
        if len(heap) >= k:
            if val > heap[0][0]:
                heapq.heapreplace(heap, (val, key))  # 替换堆顶，替换最小值
        else:
            heapq.heappush(heap, (val, key))  # 自动排序堆  下标为0的是最小元素 增长堆
    return [item[1] for item in heap]


# 给你一个字符串 s，找到 s 中最长的回文子串。
#
#
#
#  示例 1：
#
#
# 输入：s = "babad"
# 输出："bab"
# 解释："aba" 同样是符合题意的答案。
#
#
#  示例 2：
#
#
# 输入：s = "cbbd"
# 输出："bb"
#
#
#
#
#  提示：
#
#
#  1 <= s.length <= 1000
#  s 仅由数字和英文字母组成
#
#  Related Topics 字符串 动态规划 👍 5301 👎 0
"""
最长回文子串 动态规划法
https://leetcode.cn/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/
"""

# 动态规划
def longestPalindrome(s):
    """
    :type s: str
    :rtype: str
    """
    n = len(s)
    if n < 2:
        return s

    max_len = 1
    begin = 0
    # dp[i][j] 表示 s[i..j] 是否是回文串
    dp = [[False] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = True

    # 递推开始
    # 先枚举子串长度
    for L in range(2, n + 1):
        # 枚举左边界，左边界的上限设置可以宽松一些
        for i in range(n):
            # 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
            j = L + i - 1
            # 如果右边界越界，就可以退出当前循环
            if j >= n:
                break

            if s[i] != s[j]:
                dp[i][j] = False
            else:
                if j - i < 3:
                    dp[i][j] = True
                else:
                    dp[i][j] = dp[i + 1][j - 1]

            # 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
            if dp[i][j] and j - i + 1 > max_len:
                max_len = j - i + 1
                begin = i
    return s[begin:begin + max_len]

# 中心扩展
class Solution1:
    def expandAroundCenter(self, s, left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return left + 1, right - 1

    def longestPalindrome(self, s: str) -> str:
        start, end = 0, 0
        for i in range(len(s)):
            left1, right1 = self.expandAroundCenter(s, i, i)
            left2, right2 = self.expandAroundCenter(s, i, i + 1)
            if right1 - left1 > end - start:
                start, end = left1, right1
            if right2 - left2 > end - start:
                start, end = left2, right2
        return s[start: end + 1]

# Manacher 算法（马拉车算法 臂长）
class Solution2:
    def expand(self, s, left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return (right - left - 2) // 2

    def longestPalindrome(self, s: str) -> str:
        end, start = -1, 0
        s = '#' + '#'.join(list(s)) + '#'
        arm_len = []
        right = -1
        j = -1
        for i in range(len(s)):
            if right >= i:
                i_sym = 2 * j - i
                min_arm_len = min(arm_len[i_sym], right - i)
                cur_arm_len = self.expand(s, i - min_arm_len, i + min_arm_len)
            else:
                cur_arm_len = self.expand(s, i, i)
            arm_len.append(cur_arm_len)
            if i + cur_arm_len > right:
                j = i
                right = i + cur_arm_len
            if 2 * cur_arm_len + 1 > end - start:
                start = i - cur_arm_len
                end = i + cur_arm_len
        return s[start+1:end+1:2]


# 编写一个函数来查找字符串数组中的最长公共前缀。
#
#  如果不存在公共前缀，返回空字符串 ""。
#
#
#
#  示例 1：
#
#
# 输入：strs = ["flower","flow","flight"]
# 输出："fl"
#
#
#  示例 2：
#
#
# 输入：strs = ["dog","racecar","car"]
# 输出：""
# 解释：输入不存在公共前缀。
#
#
#
#  提示：
#
#
#  1 <= strs.length <= 200
#  0 <= strs[i].length <= 200
#  strs[i] 仅由小写英文字母组成
#
#  Related Topics 字符串 👍 2281 👎 0
"""
最长公共前缀 分治法
https://leetcode.cn/problems/longest-common-prefix/solution/zui-chang-gong-gong-qian-zhui-by-leetcode-solution/
"""


def longestCommonPrefix(strs):
    """
    :type strs: List[str]
    :rtype: str
    """

    def lcp(start, end):
        if start == end:
            return strs[start]

        mid = (start + end) // 2
        lcpLeft, lcpRight = lcp(start, mid), lcp(mid + 1, end)
        minLength = min(len(lcpLeft), len(lcpRight))
        for i in range(minLength):
            if lcpLeft[i] != lcpRight[i]:
                return lcpLeft[:i]

        return lcpLeft[:minLength]

    return "" if not strs else lcp(0, len(strs) - 1)


"""
347. 前 K 个高频元素
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:

输入: nums = [1], k = 1
输出: [1]

提示：
1 <= nums.length <= 105
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/top-k-frequent-elements
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
"""


class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        def sift_down(arr, root, k):
            """下沉log(k),如果新的根节点>子节点就一直下沉"""
            val = arr[root]  # 用类似插入排序的赋值交换
            while root << 1 < k:
                child = root << 1
                # 选取左右孩子中小的与父节点交换
                if child | 1 < k and arr[child | 1][1] < arr[child][1]:
                    child |= 1
                # 如果子节点<新节点,交换,如果已经有序break
                if arr[child][1] < val[1]:
                    arr[root] = arr[child]
                    root = child
                else:
                    break
            arr[root] = val

        def sift_up(arr, child):
            """上浮log(k),如果新加入的节点<父节点就一直上浮"""
            val = arr[child]
            while child >> 1 > 0 and val[1] < arr[child >> 1][1]:
                arr[child] = arr[child >> 1]
                child >>= 1
            arr[child] = val

        stat = collections.Counter(nums)
        stat = list(stat.items())
        heap = [(0, 0)]

        # 构建规模为k+1的堆,新元素加入堆尾,上浮
        for i in range(k):
            heap.append(stat[i])
            sift_up(heap, len(heap) - 1)
        # 维护规模为k+1的堆,如果新元素大于堆顶,入堆,并下沉
        for i in range(k, len(stat)):
            if stat[i][1] > heap[1][1]:
                heap[1] = stat[i]
                sift_down(heap, 1, k + 1)
        return [item[0] for item in heap[1:]]


"""
验证IPV4地址格式
https://leetcode.cn/problems/validate-ip-address/
异常情况：1. 字母；2. 前导有0，例如 01.001.100.101； 3. 四位 三个点；4. 0<= x <=255 之间
"""


def validIPAddress(queryIP: str) -> str:
    pos = queryIP.split('.')
    if len(pos) != 4:
        return "Neither"
    for x in pos:
        if not x.isdigit():  # 判断字符串是否是数字类型
            return "Neither"
        x_int = int(x)
        if len(x) != len(str(x_int)):  # 判断前导0问题
            return "Neither"
        if x_int < 0 or x_int > 255:  # 判断数字大小
            return "Neither"
    return "IPv4"


"""
题目：有 n 个整数，使其前面各数顺序向后移 m 个位置，最后 m 个数变成最前面的 m 个数
"""
def lanhu(nums: List, m: int):
    """
    [1,2,3,4]   2
    [3,4,1,2]
    :return:
    """
    l = nums[m:]
    r = nums[:m]
    return l + r


"""
题目：比较两个版本号大小。
"""
class Solution:
    def compare(self , version1: str, version2: str) -> int:
        n1 = len(version1)
        n2 = len(version2)
        i, j = 0, 0
        # 直到某个字符串结束
        while i < n1 or j < n2:
            num1 = 0
            # 从下一个点前截取数字
            while i < n1 and version1[i] != '.':
                num1 = num1 * 10 + int(version1[i])
                i += 1
            # 跳过点
            i += 1
            num2 = 0
            # 从下一个点前截取数字
            while j < n2 and version2[j] != '.':
                num2 = num2 * 10 + int(version2[j])
                j += 1
            # 跳过点
            j += 1
            # 比较数字大小
            if num1 > num2:
                return 1
            if num1 < num2:
                return -1
        # 版本号相同
        return 0


class Solution:
    def compare(self , version1: str, version2: str) -> int:
        #分割
        nums1 = version1.split('.')
        nums2 = version2.split('.')
        for i in range(max([len(nums1), len(nums2)])):
            #较短的版本号后续都取0,字符串转数字
            num1 = int(nums1[i]) if i < len(nums1) else 0
            num2 = int(nums2[i]) if i < len(nums2) else 0
            #比较数字大小
            if num1 > num2:
                return 1
            if num1 < num2:
                return -1
        #版本相同
        return 0


def str_s(strs: str) -> List[int]:
    """ {k:v, k:v} } k是字符， v是出现的次数
        {'a': 1, 'b': 1, 'c': 7, 'd': 1}
    """
    n = len(strs)
    hashmap = {}  # 所有的字符和次数
    for i in range(n):
        if strs[i] in hashmap:  # 已存在 则自增
            hashmap[strs[i]] += 1
        else:                   # 不存在则添加 并讲值置为1
            hashmap[strs[i]] = 1

    print(hashmap)
    ans = 0  # 记录最大值
    res = []  # 同时存在多个最大值时，记录所有
    for k, v in hashmap.items():
        if ans < v:
            ans = v
            res = [(k, v)]
        elif ans == v:
            res.append((k, v))
        else:
            pass
    # res = []  # 同时存在多个最大值时，记录所有
    # for k, v in hashmap.items():
    #     if ans == v:
    #         res.append((k, v))
    print(res)
    return res


if __name__ == '__main__':
    print(numWays(44))
